\chapter{分组密码(Block Ciphers)}
分组密码就是将数据序列划分为一定长度的组，然后在密钥的控制下，将数据分组变换为等长数据序列或者组。\par
1949年香浓(C.D. Shannon)在其论文《保密系统的通信理论》中提到密码设计的基本方法\footnote{香农在其文章引入扩散和混淆只要是为了阻止密码分析中的统计分析方法，可以看此文章中的第23部分“23. STATISTICAL METHODS”}，扩散(Diffusion)、混淆(Confusion)和乘积迭代\footnote{在实际应用中，为了加强密码系统的保密性，常常采用多个密码复合的方法，这就是所谓的乘积密码(product cipher)，乘积密码是m个函数的复合，其中每个函数是一个替换或换位函数。\cite{qing-cry}}。 \par

“1948年,C.E.Shannon发表了关于通信的数学理论的重要文章,标志着信息论的诞
生.1949年,他在另一篇著名文章“秘密系统的通信理论”中,指出了通信和信息加密的一
般特征,以及将信息论用于密码学的基本方法. Shannon建议交替使用代替和换位两种方
法,即他称之为混乱( confusion)和扩散( diffusion)的过程,破坏对密码系统所进行的各种
统计分析,从1968年到1975年,在Shannon这种思想的影响下,许多公司积极着手研制
保密性好的乘积密码,其中比较成功的是以Horst Feistel为首的IBM公司设计小组的产品
LUCIFER分组乘积密码( block product cipher),不久,在 LUCIFER设计的基础上,以
W. L. Tuchman 为首的 IBM 小组又在探索建立一种保密性更好的乘积密码的途径,他们研究的成果就是著名的DES。”\cite{qing-cry}

\section{Feistel结构}

当前占绝大多数的对称分组密码都是基于Feistel分组密码结构而设计，Feistel于1973年在 Scientific American 发表的论文“Cryptography and Computer Privacy”中，对其Feistel密码(也称为LUCIFER密码)设计思路进行了说明。下面我们引用William Stalling在其密码学专著\cite{stalling-cry}中的一段总结。
\par
\vspace{0.5cm}
"\textit{Feistel 提出可以用乘积密码的概念近似简单的替代密码。乘积密码就是以某种方式连续运行两个或多个密码系统，以使得所得到的最后结果或乘积，从密码编码的角度讲，比其中任意一个单独密码都强。特别地，Feistel提出用替代和置换交替的方式构造密码，实际上，这是Claude Shannon设想的一个实现，Shannon提出用扰乱(confusion)和扩散(diffusion)交替的方法构造乘积密码。下面讨论扰乱和扩散的概念以及Feistel密码。但首先应该提到一个值得注意的情况：Feistel密码结构是对25年前基于Shannon 1945年的设想提出的，而现在正在使用的几乎所有重要的对称分组密码都使用这种结构。}"
\vspace{0.5cm}
\par
Feistel结构如图\ref{Feistel-classical-structure}，首先将长度为2w的明文分组为左右两部分。右边部分直接成为下一轮运算的左边部分。同时右边部分与本轮密钥进行轮(round)函数F运算，运算结果与左边部分异或，异或结果做为下一轮运算的右边部分。

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{Feistel-classical-structure.png}
	\caption{Feistel结构}
	\label{Feistel-classical-structure}
\end{figure}

Feistel结构的解密过程与加密过程相同，只是把轮密钥倒序，也就是说，解密时，第一轮密钥用$k_n$，第二轮用$k_{n-1}$，最后一轮用$k_1$。下面我们简单证明一下这个结论的正确性。\par

对于第i轮加密，我们有：
\begin{equation}\nonumber
	\begin{aligned}
	   &L_i=R_{i-1}\\
	   &R_i=L_{i-1}\oplus F(R_{i-1},k_i)
	\end{aligned}
\end{equation}
我们把上面等式变形：
\begin{equation}\nonumber
	\begin{aligned}
	&R_{i-1}=L_i\\
	&L_{i-1}=R_i\oplus F(R_{i-1},k_i)
	\end{aligned}
\end{equation}
因为有$R_{i-1}=L_i$，所以最后我们有：
\begin{equation}\nonumber
	\begin{aligned}
	&R_{i-1}=L_i\\
	&L_{i-1}=R_i\oplus F(L_i,k_i)
	\end{aligned}
\end{equation}

上面这个式子表示，我们逆序操作即可以进行解密，由于运算结构都是相同的，所以我们也可以说将轮密钥逆序输入算法就可以解密。

从上面的推动中可以看出，我们并不要求F是一个可逆函数。即使F是一个常数函数也就解密没有影响。

Feistel网络的具体实现依赖以下选择\cite{stalling-cry}：
\begin{itemize}
	\item 分组大小：分组越大意味着安全性越高(如果其他条件相同)，但加密/解密速度也越慢。64比特分组大小是一个合理的折衷，在分组密码设计中他几乎是个通用的数值。
	\item 密钥大小：密钥长度越长则安全性越高，但加/解密速度也越慢。64比特或者更小的密钥长度现在已经被广泛认为不够安全，128比特已经成为常用的长度。
	\item 循环次数：Feistel密码的特点是一个循环不能保证足够的安全性，而循环越多则安全性越高。通常采用16次循环。
	\item 子密钥产生算法：这个算法越复杂则密码分析就应该越困难。
	\item 轮(round)函数：同样，复杂性越高则抗击密码分析的能力就越强。
\end{itemize}


Feistel密码设计中还要考虑另外两个因素\cite{stalling-cry}：

\begin{itemize}
	\item 快速的软件加密/解密：在很多情况下，加密过程被以某种方式嵌入在应用程序或工具函数中以至于没法用硬件实现，因此，算法的执行速度就成为一个重要的考虑因素。\footnote{stalling这本书是在2000年作用出版的，现在情况有所不同，越来越多的平台从芯片或者主板底层开始支持一些基本的密码运算。}
	\item 便于分析：虽然我们希望自己的算法对于密码破译来说要尽可能困难，但使算法容易分析却很有好处。我们的意思是，如果算法能够简洁地解释清楚，那么就很容易通过分析算法而找到密码分析上的弱点，也就是能够对其牢固程度有更大信心。例如，DES这个算法的功能原理就不容易分析。
\end{itemize}


\section{DES}
DES是Data Encryption Standard的所需，中文翻译为“数据加密标准”，其明文分组长度为64比特，密钥长为56比特，密文长度64比特。\par
DES的加密算法框图如\ref{DES}所示，DES首先将输入的64比特明文进行初始置换，然后将64比特分为左32比特$L_i$和右32比特$R_i$,然后进行一轮处理，处理完后，刚开始分出来的右边32比特做为下一轮处理的左32比特，也就是$L_{i+1}=R_i$，下一轮的右32比特为$R_{i+1}=L_i\oplus f(R_i,K_{i+1})$,依次进行12轮这样的变换，然后进行逆初始置换，形成最终的密文。
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{des.png}
	\caption{DES加密过程\cite{qing-cry}}
	\label{DES}
\end{figure}
\subsection{初始置换IP}
初始置换输入是64bit，输出也是64bit，初始置换表(如表\ref{DES-INIT-IP})中元素表示64bit中的第几个，原始顺序是$1,2,3,\ldots,63,64$，置换表就是调换后的顺序，其顺序是由左至右，由上到下。逆初始置换表(如表\ref{DES-INIT-IP-INV})也是同样的含义。\par

\begin{table}[htbp]
	\begin{minipage}{0.48\linewidth} 
		\centering 
		\caption{ IP } 
		\label{DES-INIT-IP}
		\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline 
			58& 50 & 42 & 34 & 26 & 18 & 10 & 2 \\ 
			\hline 
			60& 52 & 44 & 36 & 28 & 20 & 12 & 4 \\ 
			\hline 
			62& 54 & 46 & 38 & 30 & 22 & 14 & 6 \\ 
			\hline 
			64& 56 & 48 & 40 & 32 & 24 & 16 & 8 \\ 
			\hline 
			57& 49 & 41 & 33 & 25 & 17 & 9 & 1 \\ 
			\hline 
			59& 51 & 43 & 35 & 27 & 19 & 11 & 3 \\ 
			\hline 
			61& 53 & 45 & 37 & 29 & 21 & 13 & 5 \\ 
			\hline 
			63& 55 & 47 & 39 & 31 & 23 & 15 & 7 \\ 
			\hline 
		\end{tabular} 
	\end{minipage}
	\begin{minipage}{0.48\linewidth} 
		\centering 
		\caption{ $IP^{-1}$ } 
		\label{DES-INIT-IP-INV}
		\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline 
			40& 8 & 48 & 16 & 56 & 24 & 64 & 32 \\ 
			\hline 
			39& 4 & 47 & 15 & 55 & 23 & 63 & 31 \\ 
			\hline 
			38& 6 & 46 & 14 & 54 & 22 & 62 & 30 \\ 
			\hline 
			37& 5 & 45 & 13 & 53 & 21 & 61 & 29 \\ 
			\hline 
			36& 4 & 44 & 12 & 52 & 20 & 60 & 28 \\ 
			\hline 
			35& 3 & 43 & 11 & 51 & 19 & 59 & 27 \\ 
			\hline 
			34& 2 & 42 & 10 & 50 & 18 & 58 & 26 \\ 
			\hline 
			33& 1 & 41 & 9 & 49 & 17 & 57 & 25 \\ 
			\hline 
		\end{tabular} 
	\end{minipage} 
\end{table}

对于64比特长的数据，其中某个比特经过IP变换，再经过$IP^{-1}$变换，其位置应该不发生变化，我们取一个位置验证一下。\par
我们取第10个比特，查IP表，在第二行第二列，值为52，也就是第10个比特，变换后的位置为第52个比特，我们再进行逆变换。查$IP^{-1}$表，第52比特，第7行第4列，值为10，表示此比特变换到第10个比特，又回到原来位置。验证了其为逆变换。

初始置换的C语言实现参考代码如下：\par
\begin{lstlisting}
// initial permutation (IP)
const static char IP_Table[64] = {
	58, 50, 42, 34, 26, 18, 10, 2,
	60, 52, 44, 36, 28, 20, 12, 4,	
	62, 54, 46, 38, 30, 22, 14, 6, 
	64, 56, 48, 40, 32, 24, 16, 8,	
	57, 49, 41, 33, 25, 17,  9, 1, 
	59, 51, 43, 35, 27, 19, 11, 3,	
	61, 53, 45, 37, 29, 21, 13, 5, 
	63, 55, 47, 39, 31, 23, 15, 7
	};
void DES_InitialPermuteData(char* src,char* dst){
	//IP
	int i=0;
	for(i=0;i<64;i++)	
	{		
		dst[i] =src[IP_Table[i]-1];	
	}
}
\end{lstlisting}

\subsection{轮结构f函数}
轮结构(f函数)处理过程如图\ref{des-f-fun}所示。\par
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{des-f.png}
	\caption{$f(R_{i-1},K_i)$的计算 \space 或 \space 轮结构处理过程\cite{qing-cry}}
	\label{des-f-fun}
\end{figure}
轮结构中有两个置换E和P，E置换输入32bit，输出48bit，是将其中一些位重复，并进行重排，利用扩展表形式表示(如表\ref{DES-E})。P变换输入32bit，输出32bit，只是将比特位进行了重排，如表\ref{DES-P}所示。\par
\begin{table}[htbp]
		\centering 
		\caption{ 位选择表E } 
		\label{DES-E}
		\begin{tabular}{|c|c c c c|c|}
			\hline 
			32& 1 & 2 & 3 & 4 & 5 \\ 
			\hline 
			4& 5 & 6 & 7 & 8 & 9 \\ 
			\hline 
			8& 9 & 10 & 11 & 12 & 13 \\ 
			\hline 
			12& 13 & 14 & 15 & 16 & 17 \\ 
			\hline 
			16& 17 & 18 & 19 & 20 & 21 \\ 
			\hline 
			20& 21 & 22 & 23 & 24 & 25 \\ 
			\hline 
			24& 25 & 26 & 27 & 28 & 29 \\ 
			\hline 
			28& 29 & 30 & 31 & 32 & 1 \\ 
			\hline 
		\end{tabular} 
\end{table}

\begin{table}[htbp]
	\centering 
	\caption{ 换位表P } 
	\label{DES-P}
	\begin{tabular}{|c|c|c|c|}
		\hline 
		16& 7 & 20 &21  \\ 
		\hline 
		29& 12 & 28 &17  \\ 
		\hline 
		1& 15 & 23 & 26 \\ 
		\hline 
		5& 18 & 31 & 10 \\ 
		\hline 
		2& 8 & 24 & 14 \\ 
		\hline 
		32& 27 & 3 & 9 \\ 
		\hline 
		19& 13 & 30 & 6 \\ 
		\hline 
		22& 11 & 4 & 25 \\ 
		\hline 
	\end{tabular} 
\end{table}

轮结构中的S盒是DES中重要的设计部分，DES中共有8个S盒(如图\ref{DES-S}) ，每个S盒输入6bit，输出4bit。对于一个S盒的6bit输入，第一位和第六位，用来选择S盒中的一种代换方法，所以一个S盒共定义了四种代换方法，输入的另外4bit，用来确定其输出数据，我们从S定义表中的输出数据区可以看到，输出的最大数据为15，最小为0，这与输出是个4bit数据相符。
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{DES-S-BOX.png}
	\caption{S盒\cite{qing-cry}}
	\label{DES-S}
\end{figure}
\subsection{密钥生成}
DES初始密钥K是一个64位的二进制块，其中有8位奇偶校验位，对DES的64比特初始密钥进行置换选择1(PC-1)有两个作用：\par
一是将分别位于8、16、24、32、40、48、56、64的校验位去掉。\par
二是对剩余56比特进行换位。\par
$C_0$和$D_0$是将换位后的56比特密钥分为两半，各为28比特。$LS_1,LS_2,LS_9,LS_{16}$是循环左移1位变换，$LS_3,LS_4,LS_5,LS_6,LS_7,LS_8,LS_{10},LS_{11},LS_{12},LS_{13},LS_{14},LS_{15}$是循环左移2位变换,通常用一个表来表示。
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{des-key.png}
	\caption{DES加密中密钥处理过程\cite{qing-cry}}
	\label{DES-KEY}
\end{figure}
\subsubsection{置换选择1(PC-1)}
此置换输入56bit，输出56bit，置换表如\ref{DES-PC-1}所示，表的含义同初始置换表。
\begin{table}[htbp]
	\centering 
	\caption{ PC-1 } 
	\label{DES-PC-1}
	\begin{tabular}{|c|c|c|c|c|c|c|}
		\hline 
		57& 49 & 41 & 33 & 25 & 17 & 9 \\ 
		\hline 
		1& 58 & 50 & 42 & 34 & 26 & 18 \\ 
		\hline 
		10& 2 & 59 & 51 & 43 & 35 & 27 \\ 
		\hline 
		19& 11 & 3 & 60 & 52 & 44 & 36 \\ 
		\hline 
		63& 55 & 47 & 39 & 31 & 23 & 15 \\ 
		\hline 
		7& 62 & 54 & 46 & 38 & 30 & 22 \\ 
		\hline 
		14 & 6 & 61 & 53 & 45 & 37 & 29 \\ 
		\hline 
		21& 13 & 5 & 28 & 20 & 12 & 4 \\ 
		\hline 
	\end{tabular} 
\end{table}
\subsubsection{置换选择2(PC-2)}
此置换输入56bit，输出48bit，置换表如\ref{DES-PC-2}所示，表的含义同初始置换表，只是舍掉了8位，舍掉的为54，43，38，35，25，22，18，9。
\begin{table}[htbp]
	\centering 
	\caption{ PC-2 } 
	\label{DES-PC-2}
	\begin{tabular}{|c|c|c|c|c|c|}
		\hline 
		14& 17 & 11 & 24 & 1 & 5 \\ 
		\hline 
		3& 28 & 15 & 6 & 21 & 10 \\ 
		\hline 
		23& 19 & 12 & 4 & 26 & 8 \\ 
		\hline 
		16& 7 & 27 & 20 & 13 & 2 \\ 
		\hline 
		41& 52 & 31 & 37 & 47 & 55 \\ 
		\hline 
		30& 40 & 51 & 45 & 33 & 48 \\ 
		\hline 
		44& 49 & 39 & 56 & 34 & 53 \\ 
		\hline 
		46& 42 & 50 & 36 & 29 & 32 \\ 
		\hline 
	\end{tabular} 
\end{table}
\subsubsection{密钥左循环移位}
在每一轮的加密中，会将56bit密钥分为左右两半，分别对左右两半进行左循环移位，移动几位和第几轮加密有关，其对应关系如表\ref{DES-KEY-SHIFT}。
\begin{table}[htbp]
	\centering 
	\caption{ 密钥处理过程中左移位数表 } 
	\label{DES-KEY-SHIFT}
	\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
		\hline 
		轮数& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ 
		\hline 
		左移位数& 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 1 \\ 
		\hline 
	\end{tabular} 
\end{table}
\subsection{解密}
"在经过所有的代替、置换、异或和循环移动之后,你或许认为解密算法与加密算法完全
不同,并且也像加密算法一样有很强的混乱效果。恰恰相反,经过精心选择各种运算,获得
了这样一个非常有用的性质:加密和解密可使用相同的算法。\par
DES使得用相同的函数来加密或解密每个分组成为可能。两者的唯之不同是密钥的次
序相反。这就是说,如果各轮的加密密钥分别是K1,K2,K3,…,K16,那么解密密钥就
是K16,K15,K14,…,K1。为各轮产生密钥的算法也是循环的。密钥向右移动,每次移动
的个数为0,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1。\cite{schneier-应用密码学}"\par

\section{2DES}

我们将密钥为k的DES加密用$c=E_k(m)$来表示，那么二重DES加密可写为$c=E_{k_2}(E_{k_1}(m)),k_1 \neq k_2$,所以2DES的密钥长度为$56 \times 2=112$bit.

\section{3DES}

1999年美国国家标准局(NIST)发布了DES标准“DATA ENCRYPTION STANDARD (DES)”，在标准的附录二中给出了3DES的参考用法，如图\ref{T-DES}所示。

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{T-DES.png}
	\caption{NIST FIPS PUB 46-3 中Triple DES BlockDiagram}
	\label{T-DES}
\end{figure}

\section{填充}
\subsection{NoPadding} 
这种方法，API或算法本身不对数据进行处理，加密数据由加密双方约定填补算法。例如若对字符串数据进行加解密，可以补充0或者空格，然后trim。

\subsection{PKCS5Padding} 
加密时，先把数据字节长度对8取余，余数为m，若m>0,则补足8-m个字节，字节数值为8-m，即差几个字节就补几个字节，字节数值即为补充的字节数，若为0则补充8个字节的8。\par
解密后时，取最后一个字节，值为m，则从数据尾部删除m个字节，剩余数据即为加密前的原文。

\subsection{ISO 10126 padding}
ISO 10126  specifies that the padding should be done at the end of that last block with random bytes, and the padding boundary should be specified by the last byte.

Example: In the following example the block size is 8 bytes and padding is required for 4 bytes\\

... | DD DD DD DD DD DD DD DD | DD DD DD DD $\underbrace{81\ A6\ 23\ 04}_{\text{填充值}}$ |

\subsection{Zero padding}

All the bytes that are required to be padded are padded with zero. The zero padding scheme has not been standardized for encryption, although it is specified for hashes and MACs as Padding Method 1 in ISO/IEC 10118-1 and ISO/IEC 9797-1.\par

Example: In the following example the block size is 8 bytes and padding is required for 4 bytes\\

... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 00 | \\
Zero padding may not be reversible if the original file ends with one or more zero bytes, making it impossible to distinguish between plaintext data bytes and padding bytes. It may be used when the length of the message can be derived out-of-band. It is often applied to binary encoded strings as the null character can usually be stripped off as whitespace.\par

Zero padding is sometimes also referred to as "null padding" or "zero byte padding". Some implementations may add an additional block of zero bytes if the plaintext is already divisible by the block size.

\section{分组密码的运行模式}
NIST 在2001发布了一个文档“SP 800-38A Recommendation for Block Cipher Modes of Operation: Methods and Techniques”\footnote{SP是special publication的缩写}，对分组密码的运行模式进行了总结和说明，并且给出了一些运行示例，下面我们对这几种模式简单介绍。

\subsection{电码本模式(Electronic Code Book)/ECB模式}
首先对明文进行分组，最后一个分组不够64bit需要进行填充。每个明文组独立地用同一密钥加密。$M={m_1,m_2,m_3,\ldots},C={E_k(m_1),E_k(m_2),E_k(m_3),\ldots}$，如图\ref{ECB}所示。NIST标准中的图示如图\ref{NIST-ECB}所示。

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{ECB.png}
	\caption{ECB过程\cite{yang-mcry}}
	\label{ECB}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{NIST-ECB.png}
	\caption{NIST EDB图示}
	\label{NIST-ECB}
\end{figure}

NIST标准中的符号含义为：\\
\begin{itemize}
	\item $CIPH_k(X)$表示用密钥$k$对$X$进行加密操作;
	\item $CIPH_k^{-1}(X)$表示用密钥$k$对$X$进行解密操作;
	\item $\oplus$表示按位异或；
	\item $MSB_m(X)$表示比特串$X$的最高位上的$m$个比特
	\item $P_i$表示第$i$个明文块，$C_i$表示第$i$个密文块。
\end{itemize}


\subsection{密码分组链接模式(Cipher Block Chain)/CBC模式}
首先对明文进行分组，最后一个分组不够64bit需要进行填充。加密算法输入时当前明文组与前一个密文组的异或。$c_i=E_k(c_{i-1}\oplus m_i),c_0=IV$，IV为一个初始值，如图\ref{CBC}所示。NIST标准中的图示如图\ref{NIST-CBC}所示。

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{CBC.png}
	\caption{CBC过程\cite{yang-mcry}}
	\label{CBC}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{NIST-CBC.png}
	\caption{NIST CBC图示}
	\label{NIST-CBC}
\end{figure}

\subsection{密码反馈模式(Cipher Feedback)/CFB模式}
CFB模式将DES转换为流密码进行加密，所以不要进行填充，而且可以实时运行。CFB模式每次加密单元为j比特($j \leq 64$)。\par
CFB模式可以表示为:

	\[ c_1=p_1 \oplus S_j(E_k(SL_{64}(IV))) \]
	\[ c_i=p_i \oplus S_j(E_k(SL_{64}(IV \parallel c_1 \parallel \ldots \parallel c_{i-1}))),i \geq 2 \]

其中：\par
$S_j(X)$表示取X的高j位\par
$A \parallel B$表示将A和B按照高低位进行拼接，比如$11110000 \parallel 10100101= 1111000010100101=(F0A5)_{16}$\par
$SL_j(X)$表示取X的低j位\par
$E_k$表示密钥为k的DES加密算法\par
IV是一个64bit初始向量.\par
$p_i$为明文，共有j比特.\par

CFB的过程如图\ref{CFB}所示。NIST标准中的图示如图\ref{NIST-CFB}所示。

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{CFB.png}
	\caption{CFB过程\footnote{图片来源于\url{https://blog.csdn.net/chengqiuming/article/details/82355772
}}}
	\label{CFB}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{NIST-CFB.png}
	\caption{NIST CFB图示}
	\label{NIST-CFB}
\end{figure}

\subsection{输出反馈模式(Output Feedback)/OFB模式}
OFB模式也是转换为流模式处理，但是其流密钥生成独立于密文。$r_i$看成流加密的密钥，j为明文$p_i$的比特数，OFB加密过程可以写成：
\[ c_i=p_i \oplus r_i,i=1,2,\ldots \]
密钥流为：
\begin{equation}
	\begin{cases}
	  r_1=S_j(E_k(IV))\\
	  r_2=S_j(E_k(SL_{64}(IV \parallel r_1)))\\
	  r_3=S_j(E_k(SL_{64}(IV \parallel r_1 \parallel r_2)))\\
	  r_4=S_j(E_k(SL_{64}(IV \parallel r_1 \parallel r_2 \parallel r_3)))\\
	  \ldots
	\end{cases}
\end{equation}

OFB加解密框图如图\ref{OFB}所示。NIST标准中的图示如图\ref{NIST-OFB}所示。

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{OFB.png}
	\caption{OFB过程\footnote{图片来源于\url{https://blog.csdn.net/chengqiuming/article/details/82390910}}}
	\label{OFB}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{NIST-OFB.png}
	\caption{NIST OFB图示}
	\label{NIST-OFB}
\end{figure}

\subsection{计数模式(Counter Mode)/CTR模式}
这部分我们引用NIST SP 800-38A文档中的文字。

The Counter (CTR) mode is a confidentiality mode that features the application of the forward
cipher to a set of input blocks, called counters, to produce a sequence of output blocks that are
exclusive-ORed with the plaintext to produce the ciphertext, and vice versa. The sequence of
counters must have the property that each block in the sequence is different from every other
block. This condition is not restricted to a single message: across all of the messages that are
encrypted under the given key, all of the counters must be distinct. In this recommendation, the
counters for a given message are denoted$ T_1 , T_2 , … , T_n$ . Methods for generating counters are
discussed in Appendix B. Given a sequence of counters, $ T_1 , T_2 , … , T_n$, the CTR mode is
defined as follows\footnote{$CIPH_k(X)$表示用密钥$k$对$X$进行加密操作，$P_i$表示第$i$个明文块，$C_i$表示第$i$个密文块，$MSB_m(X)$表示比特串$X$的最高位上的$m$个比特。}:

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.8\textwidth]{CTR-MODE.png}
\end{figure}

In CTR encryption, the forward cipher function is invoked on each counter block, and the
resulting output blocks are exclusive-ORed with the corresponding plaintext blocks to produce
the ciphertext blocks. For the last block, which may be a partial block of u bits, the most
significant u bits of the last output block are used for the exclusive-OR operation; the remaining
b-u bits of the last output block are discarded.

In CTR decryption, the forward cipher function is invoked on each counter block, and the
resulting output blocks are exclusive-ORed with the corresponding ciphertext blocks to recover
the plaintext blocks. For the last block, which may be a partial block of u bits, the most
significant u bits of the last output block are used for the exclusive-OR operation; the remaining
b-u bits of the last output block are discarded.

In both CTR encryption and CTR decryption, the forward cipher functions can be performed in
parallel; similarly, the plaintext block that corresponds to any particular ciphertext block can be
recovered independently from the other plaintext blocks if the corresponding counter block can
be determined. Moreover, the forward cipher functions can be applied to the counters prior to the
availability of the plaintext or ciphertext data.

The CTR mode is illustrated in Figure 5.

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.8\textwidth]{CTR-MODE-1.png}
\end{figure}

\section{ZUC}
可以参考国密标准<祖冲之序列密码算法 第1部分：算法描述(GM/T 0001.1-2012)> 和国际标准ETSI(European Telecommunications Standard Institute)的标准<Sepcification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 \& 128-EIA3. Document 2: ZUC Specification>进行ZUC的学习。

阅读密码标准时，特别是初学者，根据实际经验，需要注意以下几点：
\begin{itemize}
	\item 由大到小的看：也就是先看大块，后再分解为小块看。
	\item 注意问题边界：一个问题，一个问题解决，不要在模块中来回看，可以先把别的模块的当成一个黑盒子。
	\item 注意原始文献的查看。
	\item 注意对文献的交叉查阅。
\end{itemize}

\section{SM4}
SM4是我国无线局域网标准WAPI中所采用的分组密码标准，2012年被我国商业密码标准采用，发表国密标准<GM/T 0002	SM4分组密码算法>,2016年成为国家标准<GBT32907-2016 信息安全技术-SM4分组密码算法>。\par
SM4的密钥长度和分组长度均为128比特,加密算法与密钥扩展算法都采用32轮迭代结构，以字节(8 bit)和字(32 bit)为单位进行数据处理。\par
\subsection{轮函数F}
轮函数F的输入为4个32bite字$X_0,X_1,X_2,X_3$，共128bit：
\[ F(X_0,X_1,X_2,X_3,rk)=X_0 \oplus T(X_1 \oplus X_2 \oplus X_3 \oplus rk)\]
其中T为一个合成变换:
\[ 
	T(X)=L(\tau(X))
\]
$\tau$为一个S盒($2^4 \times 2^4 $)非线性变换，$\tau$输入为32 bit，输出也为32 bit，则$\tau$变换可以表示为：
\[
	\tau(a)=S(a)
\]
L为一线性变换,输入32 bit a，输出32bit：
\[
	L(a)=a \oplus (a<<2) \oplus (a<<10) \oplus (a<<18) \oplus (a<<24) \footnote{<<表示循环左移操作。}
\]

\subsection{密钥扩展}
SM4算法加密时输入128 bit的密钥，采用32轮迭代结构，每一轮产生一个32 bit的轮密钥。\par
输入密钥为$MK=(MK_0, MK_1 ,MK_2,MK_3)$，其中$MK_i(i=0,1,2,3)$为32 bit。产生的轮密钥(round key)记为$rk_0,rk_1,\ldots,rk_{31}$,轮密钥的生成算法为：
\[(K_0,K_1,K_2,K_3)=(MK_0\oplus FK_0,MK_1 \oplus FK_1, MK_2 \oplus FK_2,MK_3 \oplus FK_3)\]
\[rk_i=K_{i+4}=K_i \oplus T^{'}(K_{i+1}\oplus K_{i+2}\oplus K_{i+3} \oplus CK_i) \]
其中变换$T^{'}$与轮函数中的T基本相同，只是将T中的L变换替换为$L^{'}$变换：
\[L^{'}(B) = B \oplus (B<<13) \oplus (B<<23)\]
在密钥扩展中$FK_i(i=0,1,2,3)$是常数(fixed key)\footnote{在下面的表达式中，$()_{16}$表示这个数用16进制形式表示}：
\[FK_0 = (A3B1BAC6)_{16}, FK_1 = (56AA3350)_{16}\]
\[FK_2 = (677D9197)_{16}, FK_3 = (B27022DC)_{16}\]
$CK_i(i=0,1,2,\ldots,30,31)$也是一组固定常数,这组数产生规则为:
\[CK_i=(ck_{i,0},ck_{i,1},ck_{i,2},ck_{i,3}),i=0,1,2,\ldots,30,31\]
\[ck_{i,j}= (4i+j) \times 7 \pmod{256}, j=0,1,2,3\]
通常在实际算法实现是$CK_i$事先计算好，存在表中使用。

\subsection{加密过程}
加密算法采用32轮迭代，每轮使用一个轮密钥，设输入明文$X=(X_0,X_1,X_2,X_3)$,输入密钥MK，产生轮密钥为$rk_i(i=0,1,2,\ldots,30,31)$，输出密文为Y，加密算法伪代码为：\\
\hspace*{2cm}for i from 0 to 31\\
\hspace*{2cm}\hspace*{1cm} $X_{i+4}=F(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i)$\\
\hspace*{2cm}$Y=R(X_{32},X_{33},X_{34},X_{35})$
\par
其中R为反序处理：
\[ R(X_{32},X_{33},X_{34},X_{35})=(X_{35},X_{34},X_{33},X_{32}) \]

\subsection{解密过程}
解密算法与加密算法相同，只是轮密钥顺序想反，解密伪代码为：\\
\hspace*{2cm}for i from 0 to 31\\
\hspace*{2cm}\hspace*{1cm} $X_{i+4}=F(X_i,X_{i+1},X_{i+2},X_{i+3},rk_{31-i})$\\
\hspace*{2cm}$Y=R(X_{32},X_{33},X_{34},X_{35})$    
\par
此处X为密文，Y为解密后的明文。